//给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。 
//
// 子数组 是数组的一段连续部分。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,0,1,0,1], goal = 2
//输出：4
//解释：
//有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,0,0,0,0], goal = 0
//输出：15
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 3 * 104 
// nums[i] 不是 0 就是 1 
// 0 <= goal <= nums.length 
// 
// Related Topics 数组 哈希表 前缀和 滑动窗口 


import java.util.*;

public class Leetcode930 {
	public int numSubarraysWithSum(int[] nums, int goal) {
        int ret = 0, sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            ret += map.getOrDefault(sum - goal, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
            System.out.println(sum + "-" + goal + "="+ (sum-goal) + " : " + map.getOrDefault(sum - goal, 0));
        }
        return ret;
    }

    public int numSubarraysWithSum2(int[] nums, int goal) {
    	int r1 = 0, r2 = 0;
        int sum1 = 0, sum2 = 0;
        int ret = 0;
        for (int l = 0; l < nums.length; l++) {
            if (r1 < l) r1 = l;
            if (r2 < l) r2 = l;

            while (r1 < nums.length && sum1 + nums[r1] < goal) {
                sum1 += nums[r1];
                r1++;
            }
            while (r2 < nums.length && sum2 + nums[r2] <= goal) {
            	if(sum2 + nums[r2]==goal) {
            		int[] show = Arrays.copyOfRange(nums, l, r2+1);
            		System.out.println(Arrays.toString(show));
            	}
                sum2 += nums[r2];
                r2++;
            }

            ret += r2 - r1;

            if (l < r1) sum1 -= nums[l];
            if (l < r2) sum2 -= nums[l];
        }
        return ret;
    }
}